package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.ListNode;

/** 
* @ClassName   : Leetcode0023 
* @author      : ganwei 
* @date        : 2020年5月13日 
* @Description : 23. 合并K个排序链表 该题为困难题型
*/
public class Leetcode0023 {
    /**
     * -解题思路,分治法
     */
	public ListNode mergeKLists(ListNode[] lists) {
    	if(lists == null || lists.length == 0){
    		return null;
    	}
    	
		return merge(lists, 0, lists.length-1);
		
    }
	
	/**
	 * 合并k个数组
	 */
	public ListNode merge(ListNode[] lists, int left, int right){
		if(left == right){
			return lists[left];
		}
		int mid = left + (right-left)/2;
		ListNode l1 = merge(lists, left, mid);
		ListNode l2 = merge(lists, mid+1, right);
		return mergeTwoLists(l1,l2);
	}
	/**
	 * -合并两个数组
	 */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2){
		if(l1 == null) return l2;
		if(l2 == null) return l1;
		if(l1.val < l2.val){
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		}else{
			l2.next = mergeTwoLists(l1,l2.next);
			return l2;
		}
	}
	
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0023 l0023 = new Leetcode0023();
    	
    }
}
